package com.llb666.java.leetcode;

/**
 * 1.有一个背包，能盛放的物品总重量为S,设有N件物品，其里量分别为w1, w2, ....wn,希望从N件物品中选择若干物品，
 * 所选物品的重量之和恰能放进该背包，即所选物品的重垣之和即是S。递归和非递归解法都能求得“背包题目”的一组解，
 * 试写岀“背包题目”的非递归解法
 *
 * 2.有一个背包，能盛放的物品总重量为S,设有N件物品，其质量分别为w1, w2, ....wn,价值是p1,p2,...pn希望从N件物品中选择若干物品，
 * 所选物品的重量之和恰能放进该背包，即所选物品的重垣之和即是S,且价值最大。递归和非递归解法都能求得“背包题目”的一组解，
 *试写岀“背包题目”的非递归解法
 * Created by 斌~
 * 2021/4/28 16:38
 */
public class 背包题目 {
    public static void main(String[] args) {
        //物品的数量
        int NUMBER=6;
        //背包的最大载重量
        int MAX_WEIGHT=21;
        //每个物品的重量
        int[] weight = {5, 3, 2, 10, 4, 2};
        //每个物品的价值
        int[] price = {11, 8, 15, 18, 13, 6};
        //贪心算法求解普通背包问题（物品可拆解）
        greedyBag(weight, price, MAX_WEIGHT, NUMBER);

        greedyBag(weight,MAX_WEIGHT);
    }

    /**
     * 最大容量算法（包里能装更多的东西）假设有恰好的情况
     * 从数组中找寻等于21的数组下标
     * @param nums {5, 3, 2, 10, 4, 2}
     * @param MAX_WEIGHT 21 ---- 4，5，10，2          4，3，3，10，2
     */
    private static void greedyBag(int[] nums, int MAX_WEIGHT) {



    }

    /**
     * 最大价值算法（包里能装更值钱的东西）
     */
    private static void greedyBag(int[] weight, int[] price, int MAX_WEIGHT, int NUMBER) {
        int i;
        double total_value=0;//可获得的最大价值
        double[] X = new double[NUMBER];//存储物品存放的结果（解向量），值为0-1

        //初始化解向量，java可以默认为0
        for(i=0;i<X.length;i++) {
            X[i]=0;
        }

        //surplus_capacity(剩余容量)
        double surplus_capacity=MAX_WEIGHT;//背包的剩余容量

        //specific(比值)定义一个数组存储单位价值
        double[] specific = new double[weight.length];

        for( i=0;i<specific.length;i++) {
            specific[i]=(double)price[i]/weight[i];//可获得小数
        }

        //将重量与价值按照单位价值 降序 重新排序（冒泡排序）
        for( i=0;i<specific.length-1;i++) {
            for(int j=i+1;j<specific.length;j++) {
                double temp=0;
                if(specific[i]<specific[j]) {
                    //单位价值降序排序
                    temp=specific[i];
                    specific[i]=specific[j];
                    specific[j]=temp;
                    //重量重新排列
                    temp=weight[i];
                    weight[i]=weight[j];
                    weight[j]=(int)temp;
                    //价值重新排序
                    temp=price[i];
                    price[i]=price[j];
                    price[j]=(int)temp;
                }
            }
        }
        //将物品按单位价值降序放入背包
        for(i=0;i<NUMBER;i++) {
            //如果第I个物品的重量大于背包的剩余容量，则表明此物品的分割，退出循环
            if(surplus_capacity<weight[i]) {
                break;
            }else {
                //物品可以整个放入，解为1
                X[i]=1;
                surplus_capacity-=weight[i];//更新背包的剩余容量
            }
        }
        //如果背包还没有被放满，则可以将此物品拆解放入（整个物品已经放不进去）
        if(i<=NUMBER) {
            X[i]=surplus_capacity/weight[i];//自动转成double型
        }
        //输出结果
        for(i=0;i<NUMBER;i++) {
            System.out.println("重量为:"+weight[i]+"  "+"价值为:"+X[i]*price[i]+"  "+"放入为:"+X[i]);
        }
        //计算最大的价值量
        for(i=0;i<NUMBER;i++) {
            total_value+=X[i]*price[i];
        }

        System.out.println("最大的价值量为:"+total_value);
    }
 }

